Leetcode 1140

class Solution {
    Integer[][][] memo;
    public int stoneGameII(int[] piles) {
        memo = new Integer[2][piles.length + 1][piles.length + 1];
        return stoneGame(piles,0,1,0);
    }
    private int stoneGame(int[] piles, int curr, int M, int alex){
        // base case 
        if(curr >= piles.length) return 0; // no more stone 
        if(memo[alex][curr][M] != null) return memo[alex][curr][M];
        int res = alex == 1 ? 1000000 : -1;
        int stones = 0;
        for(int x = 1; x <= Math.min(2 * M, piles.length - curr); x ++){
            stones += piles[curr + x - 1];
            if(alex == 0){
                res = Math.max(res,stones + stoneGame(piles,curr + x,Math.max(M,x),1));
            }else{
                res = Math.min(res,stoneGame(piles,curr + x, Math.max(M,x),0));
            }
        }
        return memo[alex][curr][M] = res;
    }
}